<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
二叉堆是一种特殊的二叉树
特点
1. 它是一个完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫结构特性。
2. 二叉堆不是最小堆就是最大堆，最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。
   所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。这叫堆特性。

最小堆基本方法：
1. 返回左子节点索引
2. 返回右子节点索引
3. 返回父节点索引
4. 插入

<script>
  const compareObj = {
    less: -1,
    bigger: 1,
    equal: 0
  }

  // 最小堆
  class MinHeap {
    heap = []

    getLeftIndex (index) {
      return index * 2 + 1
    }

    getRightIndex (index) {
      return index * 2 + 2
    }

    getParentIndex (index) {
      return Math.floor((index - 1) / 2)
    }

    insert (val) {
      if (val) {
        this.heap.push(val)
        this.shiftUp(this.heap.length - 1)
        return true
      }
      return false
    }

    shiftUp (index) {
      let pIndex = this.getParentIndex(index)
      while (index > 0 && this.compare(this.heap[index], this.heap[pIndex]) === compareObj.less) {
        this.swap(this.heap, index, pIndex)
        index = pIndex
        pIndex = this.getParentIndex(index)
      }
    }

    swap (arr, index1, index2) {
      const temp = arr[index1]
      arr[index1] = arr[index2]
      arr[index2] = temp
    }

    compare (key1, key2) {
      if (key1 === key2) {
        return compareObj.equal
      } else if (key1 < key2) {
        return compareObj.less
      } else {
        return compareObj.bigger
      }
    }

    // 删除最小值
    extract () {
      let removed = this.heap[0]
      this.heap[0] = this.heap.pop()
      this.shiftDown(0)
      return removed
    }

    shiftDown (index) {
      let current = index
      let leftIndex = this.getLeftIndex(index)
      let rightIndex = this.getRightIndex(index)

      const size = this.size()

      if (leftIndex < size && this.compare(this.heap[current], this.heap[leftIndex]) === compareObj.bigger) {
        current = leftIndex
      }

      if (rightIndex < size && this.compare(this.heap[current], this.heap[rightIndex]) === compareObj.bigger) {
        current = rightIndex
      }

      if (current !== index) {
        this.swap(this.heap, current, index)
        this.shiftDown(current)
      }
    }

    size () {
      return this.heap.length
    }
  }

  const minHeap = new MinHeap()
  minHeap.insert(2)
  minHeap.insert(1)
  minHeap.insert(7)
  minHeap.insert(3)
  minHeap.insert(5)
  minHeap.insert(4)
  minHeap.insert(6)

  // 二叉最大堆
  class MaxHeap {
    heap = []

    getLeftIndex (index) {
      return index * 2 + 1
    }

    getRightIndex (index) {
      return index * 2 + 2
    }

    getParentIndex (index) {
      return Math.floor((index - 1) / 2)
    }

    insert (val) {
      if (val) {
        this.heap.push(val)
        this.shiftUp(this.heap.length - 1)
        return true
      }
      return false
    }

    shiftUp (index) {
      let pIndex = this.getParentIndex(index)
      while (index > 0 && this.compare(this.heap[index], this.heap[pIndex]) === compareObj.bigger) {
        this.swap(this.heap, index, pIndex)
        index = pIndex
        pIndex = this.getParentIndex(index)
      }
    }

    swap (arr, index1, index2) {
      const temp = arr[index1]
      arr[index1] = arr[index2]
      arr[index2] = temp
    }

    compare (key1, key2) {
      if (key1 === key2) {
        return compareObj.equal
      } else if (key1 < key2) {
        return compareObj.less
      } else {
        return compareObj.bigger
      }
    }

    // 删除对大值
    extract () {
      let removed = this.heap[0]
      this.heap[0] = this.heap.pop()
      this.shiftDown(0)
      return removed
    }

    shiftDown (index) {
      let current = index
      let leftIndex = this.getLeftIndex(index)
      let rightIndex = this.getRightIndex(index)
      const size = this.size()

      if (leftIndex < size && this.compare(this.heap[current], this.heap[leftIndex]) === compareObj.less) {
        current = leftIndex
      }

      if (rightIndex < size && this.compare(this.heap[current], this.heap[rightIndex]) === compareObj.less) {
        current = rightIndex
      }

      if (current !== index) {
        this.swap(this.heap, current, index)
        this.shiftDown(current)
      }
    }

    size () {
      return this.heap.length
    }
  }

  const maxHeap = new MaxHeap()

  maxHeap.insert(2)
  maxHeap.insert(3)
  maxHeap.insert(1)
  maxHeap.insert(4)
  maxHeap.insert(6)
  maxHeap.insert(5)
</script>
</body>
</html>
